package com.wy;

/**
 * 算法{@link https://www.cs.usfca.edu/~galles/visualization/Algorithms.html}
 *
 * 设计原则:正确性,可读性,健壮性,高效性,低存储(CRUD)
 *
 * 评价算法的2个重要指标:时间复杂度和空间复杂度
 * 时间复杂度O():运行程序需要的时间.如单层for循环,时间复杂度为O(n);嵌套双层for循环,复杂度为O(n*n).时间复杂度不做加法
 * 空间复杂度:运行程序所需要的内存
 * 
 * 最优二叉树(哈夫曼树):将最小的2个值先组成一棵树,树的值是2个最小值的和,得到的值A再和剩下的值中最小的值B进行比较
 * 
 * <pre>
 * ->若A小于B,则将A和B再次组成一棵树,继续和剩下的值中最小的值进行比较,以此类推
 * ->若A大于B,仍需要判断剩余值中有多少值小于A
 * -->若只有B小于A,A和B可以再次组成一棵树,继续和剩下的值中最小的值进行比较
 * -->若剩余值中有多个值小于A,则这些小于A的值将另外组成一棵树
 * -->A树和B树可能一直生成自己的树,直到只有一组情况时,重新合并成一个新的树
 * ->在二叉树中,叶子节点值小的放树的左边,叶子节点值大的放树的右边
 * --->如以下数:a->3,b->24,c->6,d->20,e->34,f->4,g->12
 * ---->先a,f组成树,得7
 * ---->7和6组成树,得13
 * ---->13和12组成树,得25
 * ----->此时有20和24都小于25,20和24重新组成一棵树,得44
 * ----->44大于25和34,25和34继续组成树,的59
 * ------>最终44和59组成树
 * </pre>
 * 
 * 字典树:Tire Tree,又称单词查找树,哈希树的变种,常用于统计,查找搜索引擎中分词,词频统计,自动补全等.
 * 查找效率高,其核心思想是利用公共前缀来减少查询时间,只适合字母少的英文.而且消耗内存极大,26的次方
 * 
 * 双数组字典树:实现中日韩等文字较多的分词存储
 * 
 * AC自动机:最完美结构
 *
 * @author 飞花梦影
 * @date 2019-03-27 20:43:55
 * @git {@link https://github.com/mygodness100}
 */
public class Algorithms {

	/**
	 * 二叉树:每个节点最多有2个子树的树结构,用于实现二叉树查找.但可能会遇到单边树,即1>2>3,
	 * 若是按照下级比上级大的数排左边,那么会出现只有一边树的结构,和遍历所有数据是一样的效果 若是非数字,可根据该字符在ascii表里的位置进行比较
	 */

	/**
	 * 红黑树:变相的二叉树,即当出现二叉树的单边情况时,会自动将单边变为二叉树,但只会在当前单边增加.
	 * 如果连续3个出现单边,那么中间一个会作为一个树父节点,另外2个会变成叶子节点
	 */

	/**
	 * hash算法:根据特定的算法对需要存储的值进行hash计算,可直接定位指针,但是无法进行排序,因为hash值非数字
	 */

	/**
	 * BTree:类似于二叉树,但是他在每个节点里存储的个数并非是一个,这需要根据btree设置的度来控制
	 * 度即每个节点可以存储的数据.当该节点的数据超出这个度时,数据向上延展,且每个节点可拥有的子节点可能多于2个
	 * 该结构每个节点都会存储数据,致使每一层的key减少,而cpu一次从内存总读取的数据是有限的,存储的数据越多,
	 * 每个节点存的key就越少,故出现了B+Tree
	 */

	/**
	 * B+Tree:在BTree的基础上改进,非叶子节点不存储数据,即父节点有子节点,则数据将转移到叶子节点上,
	 * 而叶子节点将会冗余父节点,即叶子节点会出现一个相同的父节点,该冗余的节点携带数据
	 */

	/**
	 * 限流的令牌桶算法:gvaua中有RateLimiter,已经实现好的令牌桶算法.系统会以一个恒定的速度往桶里面放入令牌
	 * 当有请求需要被处理时,需要先从桶里面拿令牌, 如果令牌已经没有了,请求就会被拒绝
	 */
}